package goleetcode

import "sort"

func maxTaxiEarnings(n int, rides [][]int) int64 {
	sort.Slice(rides, func(i, j int) bool {
		return rides[i][1] < rides[j][1]
	})
	m := len(rides)
	dp := make([]int64, m + 1)
	for i := 0; i < m; i++ {
		j := sort.Search(i + 1, func(k int) bool {
			return rides[k][1] > rides[i][0]
		})
		dp[i + 1] = max(dp[i], dp[j] + int64(rides[i][1] - rides[i][0] + rides[i][2]))
	}
	return dp[m]
}